|
In graph theory, a comparability graph is an undirected graph that connects pairs of elements that are comparable to each other in a partial order. Comparability graphs have also been called transitively orientable graphs, partially orderable graphs, and containment graphs.〔, p. 105; , p. 94.〕 An incomparability graph is an undirected graph that connects pairs of elements that are not comparable to each other in a partial order. ==Definitions and characterization== For any strict partially ordered set (''S'',<), the comparability graph of (''S'', <) is the graph (''S'', ⊥) of which the vertices are the elements of ''S'' and the edges are those pairs of elements such that ''u'' < ''v''. That is, for a partially ordered set, take the directed acyclic graph, apply transitive closure, and remove orientation. Equivalently, a comparability graph is a graph that has a transitive orientation,〔; see , theorem 1.4.1, p. 12. Although the orientations coming from partial orders are acyclic, it is not necessary to include acyclicity as a condition of this characterization.〕 an assignment of directions to the edges of the graph (i.e. an orientation of the graph) such that the adjacency relation of the resulting directed graph is transitive: whenever there exist directed edges (''x'',''y'') and (''y'',''z''), there must exist an edge (''x'',''z''). One can represent any partial order as a family of sets, such that ''x'' < ''y'' in the partial order whenever the set corresponding to ''x'' is a subset of the set corresponding to ''y''. In this way, comparability graphs can be shown to be equivalent to containment graphs of set families; that is, a graph with a vertex for each set in the family and an edge between two sets whenever one is a subset of the other.〔; ; , section 6.3, pp. 94–96.〕 Alternatively,〔 and . See also , theorem 6.1.1, p. 91.〕 a comparability graph is a graph such that, for every ''generalized cycle'' of odd length, one can find an edge (''x'',''y'') connecting two vertices that are at distance two in the cycle. Such an edge is called a ''triangular chord''. In this context, a generalized cycle is defined to be a closed walk that uses each edge of the graph at most once in each direction. Comparability graphs can also be characterized by a list of forbidden induced subgraphs.〔; ; , p. 91 and p. 112.〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Comparability graph」の詳細全文を読む スポンサード リンク
|